package com.mlh.binarytree;

/**
 * @author 缪林辉
 * @date 2024/4/2 15:22
 * @DESCRIPTION
*/
// 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。
// 通过修剪二叉搜索树，使得所有节点的值在[low, high]中。
// 修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。
// 可以证明，存在 唯一的答案 。
public class TrimBST {
    //递归参数  返回值：符合条件的新节点
    //递归头：root==null
    public TreeNode method1(TreeNode root, int low, int high) {
        if(root==null){
            return null;
        }
        //本节点超出边界，去相应的左右子树找新头
        if(root.val<low){
            return method1(root.right,low,high);
        }
        if(root.val>high){
            return method1(root.left,low,high);
        }
        //本节点未超出边界，去连接左右子树返回的新头
        root.left=method1(root.left,low,high);
        root.right=method1(root.right,low,high);
        return root;
    }
}
